package day1_array.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 找到字符串中所有字母异位词
 * 滑动窗口
 * @Author: yuisama
 * @Date: 2022/3/30 18:58
 * @Description:
 */
public class Num438_FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        if (s.length() < p.length()) {
            return ret;
        }
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        // 将s和p相同长度的字符出现次数分别存入sCount和pCount数组
        for (int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i) - 'a'] ++;
            pCount[p.charAt(i) - 'a'] ++;
        }
        // 开始窗口的两个字符串为异位字符串
        if (Arrays.equals(sCount,pCount)) {
            ret.add(0);
        }
        // 最多走到s.length - p.length个长度，后面的数组长度不够p.length
        // 一定不构成异位字符串
        for (int i = 0; i < s.length() - p.length(); i++) {
            sCount[s.charAt(i) - 'a'] --;
            // 窗口向右移动一个新的字符
            sCount[s.charAt(i + p.length()) - 'a'] ++;
            if (Arrays.equals(sCount,pCount)) {
                // 相同的异位字符串的起始索引为当前i的下一个位置
                ret.add(i + 1);
            }
        }
        return ret;
    }
}
